/*
题目:俄罗斯套娃信封问题
给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。

当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

注意：不允许旋转信封。
https://leetcode.cn/problems/russian-doll-envelopes/
 */
public class MaxEnvelopes {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, new Comparator<int[]> () {
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0]) {
                    // 信封的高度降序防止同一个宽度的信封构成递增序列
                    return o2[1] - o1[1];
                }
                return o1[0] - o2[0];
            }
        });

        int row = envelopes.length;
        int num = 1;
        // 表示长度为 dLen 的最长递增子串最后一个元素的最小元素, 尽量用新元素替换掉大一点的元素
        int[] d = new int[row + 1];
        d[0] = envelopes[0][1];
        int dLen = 1;
        for (int i = 1; i < row; i++) {
            if (d[dLen - 1] < envelopes[i][1]) {
                d[dLen++] = envelopes[i][1];
            } else {
                int left = 0, right = dLen - 1;
                // 找到第一个比envelopes[i][1]大的元素并替换
                while (left <= right) {
                    int mid = left + ((right - left) >> 1);
                    if (d[mid] < envelopes[i][1]) {
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }
                d[right + 1] = envelopes[i][1];
            }
        }

        return dLen;
    }
}
